package bin_tree.NewCoder;

import bin_tree.leetcode.TreeNode;

/**
 * 将二分搜索树转为排序的双向链表
 * @author yuisama
 * @date 2021/12/12 10:07
 **/
public class ConvertTree2LinkedList {
    // 传入一个BST的根节点，就可以将其转为双向链表，且返回链表头
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null ||(pRootOfTree.left == null &&
                pRootOfTree.right == null)) {
            return pRootOfTree;
        }
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode leftTail = left;
        while (leftTail != null && leftTail.right != null) {
            leftTail = leftTail.right;
        }
        if (leftTail != null) {
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        TreeNode right = Convert(pRootOfTree.right);
        if (right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left == null ? pRootOfTree : left;
    }
}